package middle;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution_208 {

    public static void main(String[] args) {
        Trie trie = new Solution_208().new Trie();
        trie.insert("app");
        trie.insert("apple");
        trie.insert("beer");
        trie.insert("add");
        trie.insert("jam");
        trie.insert("rental");
        System.out.println(trie.search("apps"));
        System.out.println(trie.search("app"));
//        System.out.println(trie.search("b"));
//        trie.insert("apple");
//        System.out.println(trie.search("b"));
//        System.out.println(trie.search("b"));
//        System.out.println(trie.search("apple"));
//        System.out.println(trie.search("app"));
//        System.out.println(trie.startsWith("app"));
//        trie.insert("app");
//        System.out.println(trie.search("app"));

    }

    class Trie {

        private Node emptyHead;

        public Trie() {
            emptyHead = new Node(' ');
        }

        public void insert(String word) {
            Node node = emptyHead;
            char[] chars = word.toCharArray();
            for (char c : chars) {
                List<Node> children = node.children;
                if (children == null) {
                    children = new ArrayList<>();
                    node.childMap = new HashMap<>();
                }
                node.children = children;
                Integer childNodeIndex = node.childMap.get(c);
                if (childNodeIndex == null) {
                    node.childMap.put(c, children.size());
                    Node child = new Node(c);
                    children.add(child);
                    node = child;
                } else {
                    node = node.children.get(childNodeIndex);
                }
            }
            if (node.childMap == null) {
                node.childMap = new HashMap<>();
                node.children = new ArrayList<>();
            }
            if (!node.childMap.containsKey(' ')) {
                node.childMap.put(' ', -1);
            }
        }

        public boolean search(String word) {
            Node node = find(word);
            return node != null && node.childMap.containsKey(' ');
        }

        public boolean startsWith(String prefix) {
            Node node = find(prefix);
            return node != null;
        }

        private Node find(String str) {
            char[] chars = str.toCharArray();
            Node node = emptyHead;
            for (char c : chars) {
                if (node.childMap == null) {
                    return null;
                }
                Integer childNodeIndex = node.childMap.get(c);
                if (childNodeIndex == null) {
                    return null;
                }
                node = node.children.get(childNodeIndex);
            }
            return node;
        }

        class Node {
            public char c;
            public List<Node> children;
            public Map<Character, Integer> childMap;

            public Node(char c) {
                this.c = c;
            }
        }
    }
}
